This invention relates generally to language translators such as source code compilers and more particularly to translators or source code compilers which reschedule instructions.
As is known in the art, computer language translators such as compilers or assemblers convert a high level language or assembly code into a target language such as machine code which can be used to provide an executable version of a program. In particular, compilers convert high level language computer programs into machine language. That is, a compiler written for a particular high level language and computer converts the particular high level language into a machine language which is specific to the computer, whether that computer is the one on which the compiler resides or another machine.
Because compilers are written with specific hardware systems in mind, many are written to optimize the compiled code such that the compiled code takes advantage of the opportunities presented as a result of the configuration of the computer hardware. For example, in pipelined computer systems and multi-issue machines (super-scalar and very-long-instruction-word computer systems), there are often unused instruction issue slots as a result of data dependencies and resource conflicts between instructions. That is, unused issue slots occur because many instructions take more than one cycle to complete or because data and control dependencies and resource conflicts arise. Thus, while the system is waiting for an instruction to complete it is desirable to make more efficient use of the processor to issue other instructions. One approach which takes advantage of this situation involves rescheduling the order of the computer program instructions at compile time. In this way, a rescheduled instruction may be issued in a slot left empty by a prior instruction.
Typically, compilers break instructions into groups called basic blocks when identifying instructions to reschedule. All instructions in a basic block share the same control dependence. That is, these basic blocks of code have a single entry point and are typically guaranteed to execute all instructions within the block once the block has been entered.
As computers have become capable of executing an increasing number of instructions at a time, these short blocks of code do not provide enough instructions which may be rescheduled to make use of all available issue slots. In order to make additional instructions available for rescheduling, an approach has been developed called "speculative scheduling" which reschedules instructions and places them before branches on which they are control dependent. As a result, a speculatively scheduled instruction is executed before it is known whether it should be executed; that is whether in the logical flow of the program, it would have executed had it not been rescheduled. A speculatively scheduled instruction is called "mispredicted" after it is executed if it is determined that the instruction should not have executed due to a controlling branch taking an unpredicted direction.
During execution of an instruction an exception is raised if the input data to the instruction is invalid. In current implementations, if an instruction was "speculatively scheduled" and therefore "speculatively executed" and the instruction was speculatively scheduled by a compiler or other software mechanism, the exception is generally ignored. On the other hand, if the instruction was speculatively scheduled by hardware, often times the hardware will have circuits which allow the exception to be processed such that the processor can undo errant transactions. If it is shown that an instruction was "mispredicted" (i.e., that it should not have executed) then the exception should be ignored.
As mentioned above, both hardware and software techniques have been developed for speculatively executing instructions. Using a hardware technique, it is expected that the hardware will undo all side effects of mispredicted instructions and that no exception caused by a speculatively scheduled instruction will be raised until it is shown that the instruction was predicted correctly.
One problem with software techniques for speculatively scheduling instructions is that these techniques generally do not have the capability to defer exceptions caused by speculatively scheduled instructions. Therefore, software techniques either confine rescheduling to instructions that cannot generate an exception (i.e. those instructions which, due to hardware constraints, are incapable of raising an exception) or ignore all exceptions that might be generated by speculatively scheduled instructions. As a result, the benefits presently available through software techniques which speculatively schedule instructions are limited. As mentioned above, those software techniques that do attempt to reschedule instructions capable of generating exceptions typically ignore all exceptions whether the instructions are mispredicted or not.
An alternate method available to increase the number of instructions available for rescheduling is through a process called branch elimination. Branch elimination rewrites a program to preserve its original semantics using straight line code as a replacement for the conditional code found within the program. Two general classes of branch elimination may be identified, so called "hardware predication" and so called "select".
The technique referred to as "hardware predication" eliminates a branch by applying the condition expressed by a branch as a predicate to each instruction controlled by the branch. Included as part of the encoding of each instruction formerly controlled by the eliminated branch, is the location of the instruction's associated predicate which is a boolean that was formerly tested by the eliminated branch.
The "select" option of branch elimination is a combined hardware and software approach. In many computer system hardware architectures, instructions are composed of an op-code portion, two source register operand portions and a destination register operand portion. The source and destination operands serve as pointers to a general purpose register file in the processor. A "select" operation uses three inputs for source register operands: two possible input values and a predicate. The "select" operation chooses between the two input values based upon the value of the predicate. Because most architectures allocate only two source operands per instruction and a "select" operation requires three, two instructions are required on these architectures to perform a select operation: a copy instruction followed by a conditional copy instruction. The combination of the two instructions makes it possible to select between two inputs by copying a first input value to the destination and conditionally moving a second input value to the same destination.
When a "select" operation is used to eliminate branches, the instructions controlled by a branch must be executed unconditionally. As a result, these instructions may be executed before it is determined whether they would have executed in a normal encoding of the program. Therefore, these instructions are speculatively executed. As mentioned above, during execution of instructions controlled by a branch an exception may arise if the input data to the instruction is invalid.
Systems which employ "hardware predication" are generally capable of preventing side effects caused by mispredicted instructions. Generally, the hardware will include circuits which allow the exception to be processed such that the processor can undo errant transactions. Those systems which employ "select" operations, however, are not capable of preventing such side effects and are therefore usually either limited to selecting instructions which will not cause exceptions or ignoring all exceptions that may be generated by predicated instructions.